1. Field of the Invention
The present invention relates to an absolute difference accumulator circuit which is used to determine the correlation between two sets of data and other purposes.
2. Description of the Related Art
Correlation between two sets of image data has been computed for pattern matching of different image data, for example, in the field of image processing technology. Correlation between two sets of image data is determined by calculating the absolute value of the difference of pixel data at the same coordinate between the two sets of image data for each pixel, and summing up the differences. In FIG. 1, for example, to determine the correlation between two sets of image data represented by two pictures A and B, absolute values of (A.sub.1 -B.sub.1), (A.sub.2 -B.sub.2), (A.sub.3 -B.sub.3), . . . (A.sub.k -B.sub.k) . . . are calculated successively, with the absolute values of differences summed up, thereby to obtain the value which represents the correlation, where A.sub.1 through A.sub.K and B.sub.1 through B.sub.k represent the gradations of the pixel data at the respective coordinates, which may be denoted as A and B by omitting the suffix to collectively represent the image data.
Arithmetic operations as described above constitute the indispensable technique particularly in the process of detecting the motion vectors between frames, which is used in encoding of moving images.
FIG. 2 shows the construction of an absolute difference accumulator circuit of the prior art. In FIG. 2, A.sub.1, A.sub.2, . . . ,A.sub.N represent N pieces of first data each consisting of i bits, which correspond, for example, to the data of N pixels A.sub.1 through A.sub.N among the image data of picture A shown in FIG. 1. Also in FIG. 2, B.sub.1, B.sub.2, . . . ,B.sub.N represent N pieces of second data each consisting of i bits, which correspond to the data of N pixels B.sub.1 through B.sub.N among the image data of picture B shown in FIG. 1, where N and k generally have a relation of inequality N&lt;k. In FIG. 2, numerals 11, 12 , . . . , 1N denote an difference calculation circuit. Absolute difference calculation circuit 11 calculate the absolute value of A.sub.1 -B.sub.1, absolute difference calculation circuit 12 calculates the absolute value of A.sub.2 -B.sub.2, and absolute difference calculation circuit 1N calculates the absolute value of A.sub.N -B.sub.N. Multiple input adder 2 sums up all outputs of the N absolute difference calculation circuits 11, 12 , . . . ,1N. Adder 3 stores the result of addition from the multiple input adder 2 into accumulator 4 and, upon receipt of the next result of addition from the multiple input adder 2, adds the result of addition to the contents of the accumulator 4. Therefore, such a circuit as described above can be used to obtain the sum of the absolute differences in the accumulator 4, by successively entering the pixel data A.sub.1, A.sub.2, . . . ,A.sub.n and B.sub.1, B.sub.2, . . . ,B.sub.n as the image data of picture A and picture B changes.
FIG. 3 and FIG. 4 show two different compositions of the absolute difference calculation circuit 11, 12, . . . ,1N shown in FIG. 2. In FIG. 3 numeral 5 denotes an i-bit subtractor, numeral 6 denotes a bit inverter for i bits and numeral 7 denotes a +1 incrementer for the least significant bit. The bit inverter 6 and the +1 incrementer 7 are used to obtain 2's complement. Selector 8 provides as output the result of subtraction from the subtractor 5 when the result as positive sign (sign bit is 0), or provides 2's complement of the result of subtraction when the result negative sign (sign bit is 1). Accordingly absolute value of A-B is obtained.
In FIG. 4, numeral 5 denotes a subtractor which calculates A-B and numeral 9 denotes a subtractor which calculates B-A. Selector 8 provides as output the result of subtraction from the subtractor 5 when the result of subtraction of the subtractor 5 is positive (sign bit is 0), or provides as output the result of subtraction in the subtractor 9 when the result of subtraction in the subtractor 5 is negative (sign bit is 1), because the result of subtraction in the subtractor 9 becomes positive.
FIG. 5 shows an example of the circuit construction of the subtractor 5 and the subtractor 9 of the absolute difference calculation circuit shown in FIGS. 3 and 4. The subtractors 5 and 9 comprise i units of full adders (abbreviated as FA). When a carry is generated in an adder, the carry is sent from a carry output terminal C of the adder, where the carry is generated, to the carry input terminal Co of the adder of the next more significant bit. Applied to the input terminals U of the adders 21 through 2i are input data all through a1i as minuends. Applied to the input terminals V are input data b11 through b1i, each bit being inverted ("1" is replaced with "0" and "0" is replaced with "1") as subtrahends. Carry input terminal Co of the least significant bit receives data "1" so that 1 is added to the inverted bits of the input data b11 through b1i. Consequently, because the input data all through a1i and 2's complement of the input data b11 through b1i are added, the result is the difference between the input data all through a1i and 2's complement of the input data b11 through b1i. The results of subtracting operations S1 through Si and carrys Ci are provided as output at the output terminals S of the adders 21 through 2i and carry output terminals of the adder 2i of the most significant bit. If the result of subtraction is positive, carry Ci is "1" and if the result is negative the carry Ci is "0", thereby enabling it to know the sign of the result of subtraction by the carry Ci.
FIG. 6 shows the circuit construction of +1 incrementer 7 of the absolute difference calculation circuit shown in FIG. 3. The +1 incrementer 7 comprises i units of full adders (abbreviated as FA) 31 through 3i. When a carry is generated in an adder, the carry is sent from the carry output terminal Co of the adder, where the carry is generated, to a carry input terminal C of the adder where addition of the next more significant bit is performed. Applied to the input terminals U of the adders 31 through 3i are input data a21 through a2i as augends. Applied to the input terminals V of the adder 31 of the least significant bit is data "1" as addend. Thus with input terminals V of the adders 32 through 3i of other more significant bits being fixed to 0, adding operation is performed. Upon completion of the adding operation, the sums S11 through S1i and carrys C1i are provided as output at the output terminal S of the bit adders 31 through 3i and the carry terminal C of the adder 3i of the most significant bit, respectively. Input data at the carry input terminal Co of the adder 31 of the least significant bit is fixed at 0.
FIG. 7 shows the composition of the multiple input adder 2 shown in FIG. 2. In FIG. 7, 1st bit adder 41, 2nd bit adder 42, . . . , i th bit adder 4i add the value of .vertline.A-B.vertline. for the first bit, second bit, . . . , ith bit, respectively. .vertline.A-B.vertline.i represents the value of ith bit of .vertline.A-B.vertline.. The first bit adder 41 through ith bit adder 4i are multiple input adders for N inputs. The ith bit adder 4i, for example, adds the ith bits of the results of calculations by the N absolute difference calculation circuit 11 through 1N, and the first bit adder adds the first bits of the output values provided by the N absolute difference calculation circuit.
For such a multiple input adder as described above, a Wallace Tree adder circuit can be used. FIG. 8 shows an example of the composition of an 8-input multiple input adder. The 8-input adder 50 comprises an 8-input Wallace Tree adder circuit 51 and a 2-input high-speed adder (carry look-ahead adder) 52. FIG. 9 shows the circuit diagram of the 8-input Wallace Tree adder circuit 51.
The 8-input Wallace Tree adder circuit 51 comprises a 1st bit adder 61 through 8th bit adder 68, with the nth bit adder receiving the nth bit input data dn1 through dn8. Each bit adder basically comprises a plurality of 3-input adders, each of which successively adding the input data and the carry input from the bit adder of less significant bit, and sending the carry to the bit adder of more significant bit. Adders of each bit adder are arranged in a tree structure as shown in FIG. 9, where the number of inputs at the latter stage decreases to calculate and provide the outputs of carry C and sum S in the bit adder as output at the last stage. Thus adding operations can be performed efficiently with a reduced number of adders by having each bit adder to perform addition.
In the 4th bit adder 64, for example, adder 71 adds input data d41 through d43, adder 72 adds input data d44 through d46, and adder 73 adds input data d47 and d48. Adders 71 through 73 send the sum S of the input data to adders 74 and 75 and send carry C to the 5th bit adder 65. The adder 74 adds the carry C sent from the 3rd bit adder 63 and the sum S sent from the adder 71, and the adder 75 adds the carry C sent from the 3rd bit adder 63 and the sum S sent from the adders 72 and 73. The adder 74, upon addition of said data, sends the sum S to the adder 77 and sends the carry C to the 5th bit adder 65. The adder 75, upon addition of said data, sends the sum S to the adder 76 and sends the carry C to the 5th bit adder. The adder 76 adds the carry C sent from the 3rd bit adder 63 and the sum S sent from the adder 75, sends the sum S to the adder 77 and sends the carry C to the 5th bit adder. The adder 77 adds the carry C sent from the 3rd bit adder and the sum S sent from the adders 74 and 76, and provides sum S24 and carry C24 at the 4th bit as outputs. The 4th bit adder 65 through 7th bit adder 67 have identical circuit construction.
In the 8th bit adder 68, carrys C are successively added, in the adders 81 through 83 the 9th bit is added, and in adder 84 the 10th bit is added. Then sums S21 through S2A obtained in the adders of the 1st bit adder 61 through 8th bit adder 68 and the carrys C21 through C2A are summed up in the 2-input high-speed adder 52 as shown in FIG. 8, to provide the final sum as 11-bit output.
Also in the multiple input adder circuit 2, adding operation similar to that in the 8-input adder circuit 50 shown in FIG. 8 is performed. The sum S and carry C obtained in the adders of the 1st bit adder 41 through the ith bit adder 4i are summed up in the 2-input high-speed adder 40 of the carry look-ahead adder or the like, with the final sum .vertline.A-B.vertline. produced by the multiple input circuit is provided to the adder 3 as output. The carry look-ahead adder adds the addend and augend bit by bit, while at the same time calculating the carry independently, thereby to improve the speed of adding operation.
As described previously, absolute difference calculation circuit composed as shown in FIG. 3 used in an absolute difference accumulator circuit of the prior art needs an adder installed for each bit of input data and therefore requires i units of adders for the i bit subtractor as shown in FIG. 5, and i units of +1 incrementer as shown in FIG. 6, 2i units in all. When the composition as shown in FIG. 4 is employed, too, i units of adder are installed for each i-bit subtractor and therefore 2i units of adder are required for the two subtractors. Therefore, in the absolute difference accumulator circuit wherein N units of absolute difference calculation circuit shown in FIG. 2 are used, the portion of the absolute difference calculation circuit alone needs 2Ni units of adder.
As described above, the absolute difference accumulator circuit of the prior art has a problem of needing a large number of adders leading to increasing amount of circuitry, and imposing a limitation on the possible number of input data and the number of bits in each data.